Computer storage media are prone to becoming fragmented over time, which results in slower operations and higher power consumption when the processor must re-assemble fragmented logical file segments from disparate physical locations on a computer storage media. The problem exists on both disk-type and solid-state storage media, though is becoming more acute with increasing use of portable storage media that is removable from its host device. Such removable media includes, for example, SD cards, memory stick cards, SIM cards, and multimedia cards.
Traditional disk-type drives have one or more platters that rotate about a spindle. In the physical storage realm, concentric rings about the spindle are termed tracks, which are divided into physically addressable sectors that each represent a fixed amount of volume (e.g., 512 bytes) in which data may be stored. In the logical storage realm, a file is stored on the hard drive in the clusters, sometimes termed allocation units. These clusters span across several physical sectors, generally a fixed number per cluster for a particular hard drive and its implementing software. For example, in a 1 GB hard drive using a 16-bit file allocation table, there are 32 sectors and 16,384 kilobytes (rounded to 16 KB) in a single cluster. Larger hard drives have more sectors per cluster.
Each file on the computer has a record in the file allocation table (FAT), storing information about the type and status of files that have been saved to the hard drive. Each record contains a numerical reference to the beginning cluster of each file. Since many files are larger than a single cluster and must span multiple clusters, the FAT additionally holds the cluster numbers for the succeeding clusters that contain the remaining portions of the file. If there is no “next” cluster in a file chain, the FAT sets an end-of-file marker to show that the data for a given file stops and where it stops. The logical/physical table correlates the physical storage location (the sector of memory) of each logical portion of a file (the cluster of the file).
However, each cluster may only contain data from a single file, so any unused portion of a cluster remains unusable for other data, until the original file is moved or erased. For example, consider a cluster size of 16 KB and two files of sizes 30 KB and 18 KB. Each file occupies two clusters, but the first 30 KB file leaves 2 KB unused whereas the second 18 KB file leaves 14 KB unused. As more files are stored and existing files are modified and re-stored, the clusters over which a single file are stored tend to be further removed from one another physically. This is termed disk fragmentation. When clusters that make up a given file become scattered or fragmented, it takes the file allocation table longer to re-assemble the file from non-contiguous clusters, which slows down hard drive functions. Fragmentation occurs naturally over time as files are opened, closed, and modified, so computers are equipped with disk de-fragmentation software to re-arrange stored files over contiguous clusters. Over time, the FAT will reflect valid and invalid blocks and faulty segments, which slow read and write processes due to the additional movement that the read/write head must undergo to read logically sequential clusters that are not physically sequential. Typically, the FAT is located in the mass memory to which it applies, and modified by the host computer that runs it. The host reads the clusters from the mass memory FAT and directs the read/write head to the proper physical location for the logically sequential clusters. The host computer uses its own caching to re-store the clusters into more sequential physical sectors, and so after defragmentation the logical/physical table is updated to reflect the new locations of the file clusters.
Fragmentation also occurs naturally over time in solid-state storage media, such as multimedia cards, flash memory, and memory sticks to name a few. A removable media is characterized in that the media is intended to be physically separable from the computing device whose operating system reads from and writes to the removable media. Certain types of storage media are commonly characterized as being divided into pages (analogous to a sector, generally 512 or 1024 bytes), physical sectors (analogous to the sets of sectors that equal a cluster) and logical sectors (analogous to the cluster).
Each physical erase unit, the smallest memory area of a solid-state storage media that can be erased in a single operation, is subject to some type of erase cycle limit. This limit is a floor on the number of times that each erase unit may be written to and erased, within a certain statistical confidence level. Beyond that cycle limit, performance of that erase unit is not guaranteed. At least one company (M-Systems) has developed what it terms a ‘wear leveling’ algorithm to ensure that the various erase units are cycled relatively uniformly, rather than having the same erase units undergo high cycling while others are seldom used. For example, anytime any file is changed or a new file is stored on a removable media, the file allocation table is updated which uses one cycle for each erase unit occupied by that table. Unless the table is moved to different erase units, those units on which the file allocation table was repeatedly stored after each update would fail much sooner than other erase units of the same removable media. Unfortunately, wear leveling increases fragmentation, degrading performance (e.g., speed of the read/write operations) at the same time that it extends the usable life of the overall data storage media.
It is apparent that the above concerns make it difficult to define or guarantee a minimum performance for a solid-state media. Industry practice (MultiMediaCard Association) is to calculate a practical worst-case scenario for fragmentation (which includes hardware and software considerations). While this may be some measure of media performance, it is quite rough and substantially under-represents the actual performance that a user can reasonably expect given the physical capabilities of the solid-state media itself. What is needed in the art is a more efficient use of storage media that translates into a performance parameter that can be measured and readily determined.